// Written by Craig'n'Dave
using System;
using System.Collections.Generic;
// Merge sort using iteration
namespace ConsoleApp1
{
    class Program
    {
        static string[] merge_sort(string[] items)
        {
            // Split step
            List<List<string>> items_list = new List<List <string>>();
            items_list = split(items);

            // Merge step
            int index;
            List<string> new_list = new List<string>();
            while (items_list.Count != 1)
            {
                index = 0;
                // Merge pairs of lists
                while (index < items_list.Count -1)
                {
                    new_list = merge(items_list[index], items_list[index + 1]);
                    items_list[index] = new_list;
                    // Once merged, delete one of the now redundant lists
                    items_list.RemoveAt(index + 1);
                    index = index + 1;
                }
            }
            return items_list[0].ToArray();
        }

        static List<List<string>> split(string[] items)
        {
            // Every item is put into it's own list within a container list
            List<List<string>> list_of_items = new List<List<string>>();
            List<string> item;
            int index;
            // Every item is put into it's own list within a container list
            for (index = 0; index < items.Length; index++)
            {
                item = new List<string>();
                item.Add(items[index]);
                list_of_items.Add(item);
            }
            return list_of_items;
        }

        static List<string> merge(List<string> list1, List<string> list2)
        {
            // Merge two lists into a new list
            List<string> new_list = new List<string>();
            int index1 = 0;
            int index2 = 0;
            // Check each item in each list, and add the smallest item to a new list
            while ((index1 < list1.Count) && (index2 < list2.Count))
            {
                if (string.Compare(list1[index1], list2[index2]) > 0)
                {
                    new_list.Add(list2[index2]);
                    index2 = index2 + 1;
                }
                else if(string.Compare(list1[index1], list2[index2]) < 0)
                {
                    new_list.Add(list1[index1]);
                    index1 = index1 + 1;
                }
                else if(string.Compare(list1[index1], list2[index2]) == 0)
                {
                    new_list.Add(list1[index1]);
                    new_list.Add(list2[index2]);
                    index1 = index1 + 1;
                    index2 = index2 + 1;
                }
            }

            // Add left over items from the remaining list
            if (index1 < list1.Count)
            {
                for (int item = index1; item < list1.Count; item++)
                {
                    new_list.Add(list1[item]);
                }
            }
            else if(index2 < list2.Count)
            {
                for (int item = index2; item < list2.Count; item++)
                {
                    new_list.Add(list2[item]);
                }
            }
            return new_list;
        }

        // Main program starts here
        static void Main(string[] args)
        {
            string[] items = { "Florida", "Georgia", "Delaware", "Alabama", "California" };
            items = merge_sort(items);
            Console.WriteLine(String.Join(", ", items));
        }
    }
}
